package com.beck.bee.leetcode;

/**
 * Created by cdliubei@jd.com on 4/6/2017.
 */
public class SumRootToLeafNumbers129 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        SumRootToLeafNumbers129 run = new SumRootToLeafNumbers129();
        System.out.println(run.test());
    }

    public int test(){
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        return sumNumbers(treeNode1);
    }


    public class Val {
        int sum;
        int leafNum;

        public Val(int sum, int leafNum) {
            this.sum = sum;
            this.leafNum = leafNum;
        }
    }

    public int sumNumbers(TreeNode root) {
        return sum(root).sum;
    }

    public Val sum(TreeNode root) {
        if (root == null){
            return new Val(0,0);
        }
        int leafNum = 0;
        if (root.left == null && root.right == null){
            leafNum ++;
        }
        Val left = sum(root.left);
        Val right = sum(root.right);
        int leftSum = left.sum;
        int rightSum = right.sum;
        leafNum += left.leafNum + right.leafNum;
        return  new Val(leftSum + rightSum + leafNum * root.val,leafNum);
    }

}
